// 2025/3/19
// https://leetcode.cn/problems/permutations/?envType=study-plan-v2&envId=top-100-liked
// 全排列

class Solution {
    public:
        vector<bool> valid;
        vector<vector<int>> ans;
        vector<int> tmp;
        int count;
    
        void dfs(vector<int>& nums)
        {
            int n = nums.size();
            if(count == n)
            {
                ans.push_back(tmp);
                return;
            }
            for(int i = 0; i < n; i++)
            {
                if(valid[i])
                {
                    valid[i] = false;
                    count++;
                    tmp.emplace_back(nums[i]);
                    dfs(nums);
                    tmp.pop_back();
                    count--;
                    valid[i] = true;
                }
            }
        }
    
        vector<vector<int>> permute(vector<int>& nums) {
            valid.resize(nums.size(), true);
            count = 0;
            dfs(nums);
            return ans;
        }
    };